package 第六周;

/**
 * @author xhw
 */

public class 搜索旋转排序数组 {

    public static void main(String[] args) {
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        int target = 0;
        int result = search(nums, target);
        System.out.println(result);
    }
    //使用递归方法
    public static int search(int[] nums, int target) {
        return binarySearch(nums, 0, nums.length - 1, target);
    }

    private static int binarySearch(int[] nums, int left, int right, int target) {
        //首先进行索引判断左索引是否大于右索引，如果是那就说明没有可以遍历的数组了，直接退出
        if (left > right) {
            return -1;
        }
        //计算中间索引
        int mid = left + (right - left) / 2;

        //判断中间索引的值是否等于目标值，如果是那就是找到了
        if (nums[mid] == target) {
            return mid;
        }

        //判断左边是否有序
        if (nums[left] <= nums[mid]) {
            //判断目标值在左边
            if (target >= nums[left] && target < nums[mid]) {
                //递归调用
                return binarySearch(nums, left, mid - 1, target);
            } else {
                //递归调用
                return binarySearch(nums, mid + 1, right, target);
            }
        } else {
            //判断目标值在右边
            if (target > nums[mid] && target <= nums[right]) {
                //递归调用
                return binarySearch(nums, mid + 1, right, target);
            } else {
                //递归调用
                return binarySearch(nums, left, mid - 1, target);
            }
        }

        }
    }

//
//    public static int search(int[] nums, int target) {
//        int left = 0, right = nums.length - 1;
//
//        while (left <= right) {
//            int mid = (left + right) / 2;
//            if (nums[mid] == target) {
//                return mid;
//            }
//
//            // 判断哪一部分是有序的
//            if (nums[left] <= nums[mid]) { // 左侧有序
//                if (target >= nums[left] && target < nums[mid]) {
//                    right = mid - 1;
//                } else {
//                    left = mid + 1;
//                }
//            } else {
//                if (target > nums[mid] && target <= nums[right]) {
//                    left = mid + 1;
//                } else {
//                    right = mid - 1;
//                }
//            }
//        }
//        return -1;
//    }

